package com.example.demo.zaqizabatest.sort;

import java.util.Arrays;

/**
 * @ClassName InsertSort
 * @Author lys4134
 * @Date 2022/03/04 14:19:31
 * @Description SelectSort
 * @Version 1.0
 **/
public class InsertSort {

    public static void main(String[] args) {
        int[] nums = new int[]{-1, 3, 20, 9, 10};
        sort(nums);
        System.out.println(Arrays.toString(nums));
    }

    /**
     * 从第二个值开始，往前面的数插入，当比前一位的数小，就交换位置
     *
     * @param nums
     */
    public static void sort(int[] nums) {
        for (int i = 0; i < nums.length - 1; i++) {
            int insertIndex = i + 1;
            while (insertIndex > 0) {
                if (nums[insertIndex] < nums[insertIndex - 1]) {
                    swap(nums, insertIndex, insertIndex-1);
                    insertIndex--;
                } else {
                    break;
                }
            }
        }
    }


    /**
     * 交换位置
     *
     * @param nums
     * @param i
     * @param j
     */
    public static void swap(int[] nums, int i, int j) {
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }

}
